package 力扣_中等题;

/**
 * @author 连安利
 * @version 1.0
 * @date 2021/3/19 19:42
 */
public class 最长回文子串 {
    public static void main(String[] args) {
        String s = "abbbca";
        System.out.println(longestPalindrome(s));
    }
    public static String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        int begain = 0;
        int maxlen = 1;
        boolean [][] dp = new boolean[len][len];//初始化回文表
        for(int i = 0; i < len; i++){
            //另对角线都为true
            dp[i][i] = true;
        }
        char[] charArrary = s.toCharArray();//将s字符串转化成char数组
        for(int j = 1; j < len; j++){
            for(int i = 0; i < len; i++){
                if(charArrary[i] != charArrary[j]){
                    //如果左右边界不相等，则不是回文数
                    dp[i][j] = false;
                }
                else{
                    if(j - i < 3){
                        //如果左右边界的相差小于3，及剩下 1 个或者 2 个的时候，都是回文数
                        dp[i][j] = true;
                    }
                    else{
                        //剩下的如果左右边界相等，那么就看左右边界往里缩小是否也相等，因为回文数去掉头和尾后还是回文数
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 只要dp[i][j] = true 成立，那么表示子串s [i...j]是回文数，此时记录回文启示位置和回文长度
                if(dp[i][j]&&j-i+1>maxlen){
                    begain = i;
                    maxlen = j-i+1;
                }
            }
        }

        return s.substring(begain,begain+maxlen);

    }
}
